package com.barry.algorithm.sort;

/**
 * 类功能描述：归并排序算法
 *
 * @author WangXueXing create at 19-9-4 下午5:06
 * @version 1.0.0
 */
public class MergeSort {
    /**
     * 归并排序算法
     * 将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，
     * 得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
     * 综上可知：归并排序其实要做两件事：（1）“分解”——将序列每次折半划分。（2）“合并”——将划分后的序列段两两合并后排序。
     * @param a
     * O(nlogn)
     */
    public static void mergeSort(int[] a){
        sort(a, 0, a.length-1);
        System.out.println("归并排序：");
        for (int k : a) {
            System.out.print(k+" ");
        }
    }
    //分段 将一个数组分成2个数组
    public static void sort(int[] nums,int low,int high){
        int mid = (high+low)/2;
        if(low < high){
            sort(nums, low, mid);
            sort(nums, mid+1, high);
            merge(nums, low, mid, high);
        }
    }
    // 分段排序 再合起来
    public static void merge(int[] array,int low,int mid,int high){
        int i=low; //第一段序列下标
        int j=mid+1; //第二段序列下标
        int k=0; //第三段序列下标
        int[] array2 = new int[high - low + 1]; //新序列
        while(i<=mid && j<=high){ //把两个子序列的头元素比较，取较小者进入新序列，然后在旧序列中跳过这个较小值，开始下一次比较
            if(array[i] <= array[j]){
                array2[k++] = array[i++];
            }
            else{
                array2[k++] = array[j++];
            }
        }
        if(i <= mid){ //说明上面是j溢出退出循环，即序列1还未比较完
            while(i<=mid){ //若第一段序列还没扫描完，将其全部复制到合并序列
                array2[k++] = array[i++];
            }
        }
        else if(j <= high){
            while(j<=high){ //若第二段序列还没扫描完，将其全部复制到合并序列
                array2[k++] = array[j++];
            }
        }
        for(k=0;k<array2.length;k++){
            array[k+low] = array2[k];//将分段排序的新数组复制到之前数组
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{2,3,6,4,7,5,1};
        mergeSort(a);
    }
}
